# 조인의 원리

# 중첩 루프 조인 (Nested Loop Join)

정의

중첩 루프 조인은 프로그래밍에서 사용하는 반복문과 유사한 방식으로 조인을 수행합니다.

랜덤 접근에 대한 비용이 많이 증가하므로 대용량의 테이블에서는 사용하지 않습니다.
반복문 외부에 있는 테이블을 선행테이블 또는 외부 테이블(Outer Table)이라고 하고,반복문 내부에 있는 테이블을 후행테이블 또는 내부 테이블(Inner Table)이라고 합니다.

선행테이블에서 조건을 만족하는 첫 번째 행을 찾습니다.
1. 이때 선행 테이블에 주어진 조건을 만족하지 않는 경우 해당 데이터는 필터링 됩니다.
선행테이블의 조인키를 가지고 후행 테이블에 조인키가 존재하는지 찾습니다.
1. 이후 조인을 시도합니다.
후행 테이블의 인덱스에 선행테이블의 조인 키가 존재하는지 확인합니다.
1. 존재하지 않으면 필터링
인덱스에서 추출한 레코드 식별자를 이용하여 후행 테이블을 엑세스합니다.
1. 인덱스 스캔을 통한 테이블 액세스 후행 테이블에 주어진 조건까지 모두 만족하면 해당 행을 추출버퍼에 넣습니다.

즉, 선행테이블의 조건을 만족하는 행을 추출하여 후행 테이블을 읽으면서 조인을 수행하고, 해당 작업은 선행 테이블의 조건을 만족하는 모든 행의 수만큼 반복 수행됩니다.
NL Join에서는 선행 테이블의 조건을 만족하는 행의 수가 많으면, 그 만큼 후행 테이블의 조인 작업은 반복 수행된됩니다.
따라서 결과 행의 수가 적은 테이블을 조인 순서상 선행 테이블로 선택하는 것이 전체 일량을 줄일 수 있습니다.
성공하면 바로 조인 결과를 사용자에게 보여 줄 수 있다. 그래서 결과를 가능한 빨리 화면에 보여줘야 하는 온라인 프로그램에 적당한 조인 기법

정의

정렬 병합 조인이란 각각의 테이블을 조인할 필드 기준으로 정렬하고 정렬이 끝난 이후에 조인 작업을 수행하는 조인입니다.

NLJoin은 랜덤 엑세스 방식이고, Sort Merge Join은 스캔 방식이기에, Sort Merge Join은 랜덤 엑세스로 NL Join에서 부담이 되던 넓은 범위의 데이터를 처리할 때 이용되던 조인 기법입니다.
조인을 할 때 쓸 적절한 인덱스가 없고 대용량의 테이블들을 조인하고 조인 조건으로 <, > 등 범위 비교 연산자가 있을 때 씁니다.
Sort Merge Join은 정렬할 데이터가 많아 메모리에서 모든 정렬 작업을 수행하기 어려운 경우에는 임시 영역(디스크)를 사용하기 때문에 성능이 떨어질 수 있습니다.
- 대량의 조인 작업에서 정렬 작업을 필요로 하는 Sort Merge Join보다 CPU 작업 위주로 처리하는 Hash Join이 성능상 유리합니다.
- 그러나 Sort Merge Join은 비동등 조인에 대해서도 조인 작업이 가능하다는 장점이 있습니다.
Sort Merge Join은 조인 컬럼의 인덱스를 사용하지 않기 때문에 조인 컬럼의 인덱스가 존재하지 않을 경우에도 사용할 수 있는 조인 기법입니다.

정의

해시 조인은 해시 테이블을 기반으로 조인하는 방법입니다.

생성된 해쉬 테이블의 크기가 메모리에 적재할 수 있는 크기보다 커지면 임시 영역(디스크)에 해쉬 테이블을 저장합니다.
- 따라서 두 개의 테이블을 조인한다고 했을 떄 하나의 테이블이 메모리에 온전히 들어간다면 보통 중첩 루프 조인보다 더 효율적입니다.
  - 메모리에 올릴 수 없을 정도로 크다면 디스크를 사용하는 비용이 발생됩니다.
HashJoin은 인덱스가 존재하지 않는 경우에도 사용할 수 있는 조인 기법입니다.
해쉬 함수를 이용하여 조인을 수행하기 때문에 "="로 수행하는 조인 즉, 동등 조인에서만 사용할 수 있습니다.
조인을 수행할 테이블의 조인 컬럼을 기준으로 해쉬 함수를 수행하여 서로 동일한 해쉬 값을 갖는 것들 사이에서 실제 값이 같은지를 비교하면서 조인을 수행합니다.
Hash Join은 NL Join의 랜덤 엑세스 문제점과 Sort Merge Join의 문제점인 정렬 작업의 부담을 해결하기 위한 대안으로 등장했흡니다.

MySQL의 경우 MySQL8.0.18 릴리스와 함께 이 기능을 사용할 수 있게 되었습니다.

정의

빌드 단계는 입력 테이블 중 하나르 기반으로 메모리 내 해시 테이블을 빌드하는 단계입니다.

예를 들어 persons와 countries라는 테이블을 조인한다고 했을 때 둘중 바이트가 저 작은 테이블을 기반으로 해서 테이블을 빌드합니다.
조인에 사용되는 필드가 해시 테이블의 키로 사용됩니다. 여기서는 countries.country_id가 조인 조건이며, 테이블의 키로 사용됩니다.

정의

프로브 단계 동안 레코드 읽기를 시작하며, 각 레코드에서 countries.country_id 값에 일치하는 레코드를 찾아서 결과 값으로 반환합니다.